package leetcode_600;

import helpclass.TreeNode;

/**
 *@author 周杨
 *FindModeInBinarySearchTree_501
 *describe:AC 74% 遍历两次
 *2018年9月4日 下午8:01:00
 */
public class FindModeInBinarySearchTree_501 {
	    int max_frequency = 0;
	    int max_counter = 0;
	    
	    Integer last_value;
	    int last_frequency = 0;
	    
	    int[] result;
	    int result_idx = 0;
	    
	    // in-order traversal, values will be sorted order
	    public void findMaxFrequency(TreeNode root) {
	        if(root == null)
	            return;
	        
	        // traverse left
	        findMaxFrequency(root.left);
	        
	        // analyze sequence value
	        if(last_value == null || root.val != last_value) {
	            // value changed, reset counters
	            last_frequency = 1;
	        } else {
	            // same value as previous
	            last_frequency++;
	        }
	        
	        if(max_frequency < last_frequency) {
	            max_frequency = last_frequency;
	            max_counter = 1;
	        } else if(max_frequency == last_frequency) {
	            max_counter++;
	        }
	        
	        last_value = root.val;
	        
	        // traverse right
	        findMaxFrequency(root.right);
	    }
	    
	    public void fillValues(TreeNode root) {
	        if(root == null)
	            return;
	        
	        // traverse left
	        fillValues(root.left);
	        
	        // analyze sequence value
	        if(last_value == null || root.val != last_value) {
	            // value changed, reset counters
	            last_frequency = 1;
	        } else {
	            // same value as previous
	            last_frequency++;
	        }        
	        
	        if(last_frequency == max_frequency) {
	            result[result_idx++] = root.val;
	        }
	        
	        last_value = root.val;
	        
	        // traverse right
	        fillValues(root.right);        
	    }
	    
	    public int[] findMode(TreeNode root) {
	        // first pass - find out the maximum frequency
	        findMaxFrequency(root);
	        
	        // second pass - fill array
	        result = new int[max_counter];
	        last_value = null;
	        fillValues(root);
	        
	        return result;
	    }
}
